package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.BinaryTreeNode;

/**
 * 二叉搜索树与双向链表
 *
 * @author yuhushuan
 * @date 2020/6/22 15:37
 */
public class _36_1_ConvertBinarySearchTree {


    private static BinaryTreeNode convert(BinaryTreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        // 1. 将左子树构造成双向链表，并返回链表头节点（递归完成后先输出左节点）
        BinaryTreeNode left = convert(root.left);
        if (left != null){
            // 2. 定位至左子树双向链表最后一节点
            BinaryTreeNode p = left;
            while (p.right != null) {
                p = p.right;
            }
            // 3. 如果左子树链表不为空的话，将当前 root 追加到左子树链表
            p.right = root;
            root.left = p;
        }
        // 4. 将右子树构造成双向链表，并返回链表头节点
        if (root.right != null) {
            BinaryTreeNode right = convert(root.right);
            // 5. 如果右子树链表不为空的话，将该链表追加到 root 节点之后
            root.right = right;
            right.left = root;
        }
        return left != null ? left : root;
    }


    public static void main(String[] args) {
        test1();
    }

    private static void test1() {
        BinaryTreeNode n4 = new BinaryTreeNode(4);
        BinaryTreeNode n6 = new BinaryTreeNode(6);
        BinaryTreeNode n8 = new BinaryTreeNode(8);
        BinaryTreeNode n10 = new BinaryTreeNode(10);
        BinaryTreeNode n12 = new BinaryTreeNode(12);
        BinaryTreeNode n14 = new BinaryTreeNode(14);
        BinaryTreeNode n16 = new BinaryTreeNode(16);

        n10.left = n6;
        n10.right = n14;

        n6.left = n4;
        n6.right = n8;

        n14.left = n12;
        n14.right = n16;

        print(n10);

    }

    private static void print(BinaryTreeNode root) {
        System.out.println("二叉树：");
        BinaryTreeNode.drawBinaryTree(root);
        BinaryTreeNode head = convert(root);
        System.out.println(toString(head));
    }

    public static String toString(BinaryTreeNode node) {
        if (node == null) {
            return "null";
        }
        StringBuilder sb = new StringBuilder();
        sb.append('[').append(node.value);
        while (node.right != null) {
            node = node.right;
            sb.append(", ");
            sb.append(node.value);
        }
        sb.append(']');

        sb.append('\n');
        sb.append('[').append(node.value);
        while (node.left != null) {
            node = node.left;
            sb.append(", ");
            sb.append(node.value);
        }
        sb.append(']');
        return sb.toString();
    }

}
